import java.util.Arrays;
import java.util.PriorityQueue;

/**
* @description: 826. 安排工作以达到最大收益
* @author hewei
* @date 2022/8/31 14:24
* @version 1.0
*/

public class MaxProfitAssignment {

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> {
            if (profit[a] == profit[b]) return difficulty[a] - difficulty[b];
            return profit[b] - profit[a];
        });
        for (int i = 0; i < profit.length; i++) {
            heap.add(i);
        }
        Arrays.sort(worker);
        int index = worker.length - 1;
        int ans = 0;
        while (!heap.isEmpty() && index >= 0) {
            Integer poll = heap.poll();
            if (difficulty[poll] > worker[index]) continue;
            int l = 0;
            int r = index;
            while (l < r) {
                int mid = (r - l) / 2 + l;
                if (worker[mid] >= difficulty[poll]) {
                    r = mid;
                } else l = mid + 1;
            }
            ans += profit[poll] * (index - l + 1);
            index = l - 1;
        }
        return ans;
    }
}
